#include "maxSteelPrice.h"
long maxSteelPriceError(int *price, int n) {
  if (n <= 0)
    return 0;
  long maxPrice = 0;
  for (int i = 1; i <= n / 2 + 1; i++) {
    long cuttedPrice = 0;
    if (n - i > 0)
      cuttedPrice = price[n - i - 1] + price[i - 1] > price[n - 1]
                        ? price[n - i - 1] + price[i - 1]
                        : price[n - 1];
    else
      cuttedPrice = price[n - 1];
    if (cuttedPrice > maxPrice)
      maxPrice = cuttedPrice;
  }
  return maxPrice;
}
long maxSteelPrice(int *price, int n) {
  if (n <= 0)
    return 0;
  long maxPrice = 0;
  for (int i = 1; i <= n; i++) {
    long cuttedPrice = maxSteelPrice(price, n - i);
    maxPrice = cuttedPrice + price[i - 1] > maxPrice
                   ? cuttedPrice + price[i - 1]
                   : maxPrice;
  }
  return maxPrice;
}
long maxSteelPriceMem(int *price, int n, long *dp) {
  if (n == 0)
    return 0;
  if (dp[n - 1] == -1) {
    for (int i = 1; i <= n; i++) {
      long cuttedPrice = maxSteelPriceMem(price, n - i, dp) + price[i - 1];
      dp[n - 1] = cuttedPrice > dp[n - 1] ? cuttedPrice : dp[n - 1];
    }
  }
  return dp[n - 1];
}
long maxSteelPriceMem(int *price, int n) {
  long *dp = new long[n]();
  fill(dp, dp + n, -1);
  int res = maxSteelPriceMem(price, n, dp);
  delete[] dp;
  return res;
}
long maxSteelPriceRod(int *price, int n) {
  if (n == 0)
    return 0;
  long *dp = new long[n+1];
  fill(dp, dp + n, -1);
  dp[0] = 0;
  for (int i = 1; i <= n; i++) {
    long maxPrice = -1;
    for (int index = 1; index <= i; index++) {
      maxPrice = maxPrice > price[index - 1] + dp[i - index]
                     ? maxPrice
                     : price[index - 1] + dp[i - index];
    }
    dp[i] = maxPrice;
  }
  long res = dp[n];
  delete[] dp;
  return res;
}
// long maxSteelPriceRod(int *price, int n) {
//   long *dp = new long[n]();
//   fill(dp + 1, dp + n, -1);
//   for (int i = 1; i <= n; i++) {
//     long maxPrice = -1;
//     for (int index = 0; index < i; index++) {
//       maxPrice = maxPrice > price[i - 1] + dp[i - index - 1]
//                      ? maxPrice
//                      : price[i - 1] + dp[i - index - 1];
//     }
//     dp[i] = maxPrice;
//   }
//   long res = dp[n - 1];
//   delete[] dp;
//   return res;
// }